package day_2022_4_to_7.nowcoder;

/**
 * 链表中倒数第k个结点
 * @author haomin
 * @date 2022/04/15 16:13
 **/
public class FindKthToTail_11f {
    // 遍历数组
    public ListNode FindKthToTail1(ListNode head,int k) {
        if(head == null){
            return null;
        }
        // 记录节点总数
        int count = 0;
        for(ListNode x = head ; x != null;x = x.next){
            count ++;
        }
        // 如果节点总数小于k ，说明不存在该节点
        if(count < k){
            return null;
        }
        // 找到倒数第k 个节点，（找到第（n-k）个节点）
        for(int i = 0;i < count - k;i ++){
            head = head.next;
        }
        return head;
    }

    // 前后指针法
    public ListNode FindKthToTail2(ListNode head,int k) {
        if(head == null){
            return null;
        }
        // 前后指针
        ListNode first = head;
        ListNode second = head;
        // 先让前指针走k 步
        while(k > 0 && first != null){
            first = first.next;
            k--;
        }
        // 然后前后指针一起向后走，当前指针走到末尾，后指针刚好走到倒数第 k的位置
        while(first != null){
            first = first.next;
            second = second.next;
        }
        // 程序走到这一步
        // 如果k>0，说明k大于节点总数，不存在该节点
        return k > 0 ? null : second;
    }
}